The present invention relates to the field of electronic devices having a memory array, and is more specifically directed to methods and circuits for storing and retrieving a large amount of data that needs to be accessed sequentially.
The size of a digital representation of uncompressed video images depends on the resolution and color depth of the image. A movie composed of a sequence of uncompressed video images, and accompanying audio signals, quickly becomes too large to fit entirely onto conventional recording medium, such as a compact disk (CD). Moreover, transmitting such an uncompressed movie over a communication link is prohibitively expensive because of the large quantity of data to be transmitted and the bandwidth required to do so.
It is therefore advantageous to compress video and audio sequences before they are transmitted or stored. A great deal of effort is being expended to develop systems to compress these sequences. There are several coding standards currently used that are based on the DCT algorithm, including MPEG-1, MPEG-2, H.261, and H.263. (MPEG is an acronym for "Motion Picture Expert Group", a committee of the International Organization for Standardization, ISO.) The MPEG-1, MPEG-2, H.261 and H.263 standards include decompression protocols that describe how an encoded (i.e. compressed) bitstream is to be decoded (i.e. decompressed). The encoding can be done in any manner, as long as the resulting bitstream complies with the standard.
Video and/or audio compression devices (hereinafter encoders) are used to encode the video and/or audio sequence before the sequence is transmitted or stored. The resulting encoded bitstream is decoded by a video and/or audio decompression device (hereinafter decoder) before the video and/or audio sequence is output. A bitstream can only be decoded by a decoder if the bitstream complies with the standard used by the decoder. To be able to decode the bitstream on a large number of systems, it is advantageous to encode the video and/or audio sequences according to a well accepted encoding/decoding standard. The MPEG standards are currently well accepted standards for one way communication. H.261, and H.263 are currently well accepted standards for two way communication, such as video telephony.
Once decoded, the decoded video and audio sequences can be played on an electronic system dedicated to video and audio playback, such as a television or a digital versatile disc (DVD) player, or on an electronic system where image display and audio is just one feature of the system, such as a computer. A decoder needs to be added to these electronic systems to allow them to decode the compressed bitstream into uncompressed data, before it can be played back. An encoder needs to be added to allow such electronic systems to compress video and/or audio sequences that are to be transmitted or stored. Both the encoder and decoder need to be added for two way communication.
The encoded bitstream for video contains compressed pictures. A picture is a data structure representing the encoded data for one displayable image in the video sequence. As shown in FIG. 1, a picture 100 is collection of three two-dimensional arrays of pixels, one array for luminance samples 102 and two arrays for chrominance samples 104, 106, i.e., color difference samples. The picture is typically further subdivided into smaller subunits, such as macroblocks 110. A macroblock is a data structure having a 16.times.16 array of luminance samples 112 and two 8.times.8 arrays of associated chrominance samples 114, 116. The macroblock 110 in an encoded picture contains a header portion having motion compensation information and 6 block data structures of encoded data. A block is the basic unit for DCT based transform coding and is a data structure encoding an 8.times.8 sub array of pixels. A macroblock represents four luminance blocks 118, 120, 122, 124 and two chrominance blocks 114, 116.
The chrominance samples are typically sampled at half the sampling rate of the luminance samples in both vertical and horizontal directions, producing a sampling mode of 4:2:0 (luminance:chrominance:chrominance). The color difference can also be sampled at other frequencies, for example one-half the sampling rate of the luminance in the vertical direction and the same sampling rate as the luminance in the horizontal direction, producing a sampling mode of 4:2:2.
Both MPEG-1 and MPEG-2 support multiple types of coded pictures: Intra (I) pictures, Forward Predicted (P) pictures, and Bidirectionally Predicted (B) pictures. I pictures contain only intrapicture coding. P and B pictures may contain both intrapicture and interpicture coding. I and P pictures are used as reference pictures for interpicture coding.
Intrapicture coding for I pictures involves the reduction of redundancy between the original pixels in the macroblocks using block based DCT techniques, although other coding techniques can be used. For P and B pictures, intrapicture coding involves using the same DCT based techniques to remove redundancy between interpicture prediction error pixels.
In interpicture coding, the redundancy between two pictures is eliminated as much as possible and the residual differences, i.e., interpicture prediction errors, between the two pictures are transmitted. In scenes where objects are stationary, the pixel values in adjacent pictures will be approximately equal. In scenes with moving objects, block based motion compensated prediction, based on macroblocks, is used. For each macroblock in a P picture, the best matching 16.times.16 block in the previous picture, (called the prediction block) is found, and the resultant macroblock prediction error is then encoded. The match is determined by searching in the previous picture over a neighborhood of the pixel origin of the current macroblock. The motion vectors between the current macroblock and the prediction block are also transmitted in interpicture coding that uses motion compensation. The motion vectors describe how far, and in what direction, the macroblock has moved compared to the prediction block. As shown in FIG. 2, for B pictures the best matching block 142, the prediction block, in the previous picture 140 and the best matching block 148, the prediction block in the future picture 146 is found, and averaged. This may then be summed with a set of decoded error terms of the block data structures of macroblock 152 to produce the macroblock 152 in the current picture 150. This entire process is referred to as motion compensation.
Once a picture is decoded it can be displayed, typically on a display screen in, or connected to, the electronic system by reading words of data in the picture out of memory and sending them to the display.